package _021_11_18

import (
	"strings"
)

func mySort(path [][]int) {
	for i := 0; i < len(path); i++ {
		temp := 0
		for j := 0; j < len(path)-i; j++ {
			if path[temp][0] < path[j][0] {
				temp = j
			}
		}
		_temp := path[len(path)-i-1]
		path[len(path)-i-1] = path[temp]
		path[temp] = _temp
	}
}

func back(pos []int, m [][][]int, n int, key []string, path [][]int, ret *[]int) {

	if len(key) == n {
		tempPath := make([][]int, len(path))
		for i := 0; i < len(path); i++ {
			tempPath[i] = path[i]
		}

		mySort(tempPath)
		for i := 1; i < len(tempPath); i++ {
			if tempPath[i-1][1]+1 != tempPath[i][0] {
				return
			}
		}
		*ret = append(*ret, tempPath[0][0])
		return
	}

	for i := 0; i < len(m[n]); i++ {
		path = append(path, m[n][i])
		back(m[n][i], m, n+1, key, path, ret)
		path = path[0 : len(path)-1]
	}
}

func getAllSubStr(str string, word string) [][]int {
	id := 0
	pos := make([][]int, 0)
	temp := ""
	for id < len(str) {
		temp = str[id:]
		ret := strings.Index(temp, word)
		if ret < 0 {
			break
		}
		pos = append(pos, []int{id + ret, id + ret + len(word) - 1})
		id += 1
	}

	for i := 0; i < len(pos)-1; i++ {
		for j := i + 1; j < len(pos); {
			if pos[i][0] == pos[j][0] && pos[i][1] == pos[j][1] {
				copy(pos[j:], pos[j+1:])
				pos = pos[:len(pos)-1]
				continue
			}
			j++
		}
	}

	return pos
}

//func findSubstring(s string, words []string) []int {
//	pos := make([][][]int, len(words))
//	for i := 0; i < len(words); i++ {
//		ret := getAllSubStr(s, words[i])
//		pos[i] = ret
//	}
//	ret := make([]int, 0)
//	back([]int{}, pos, 0, words, [][]int{}, &ret)
//	dupM := make(map[int]uint8)
//	for i := 0; i < len(ret); i++ {
//		if _, ok := dupM[ret[i]]; ok {
//			copy(ret[i:], ret[i+1:])
//			ret = ret[:len(ret)-1]
//			i--
//			continue
//		}
//		dupM[ret[i]] = 1
//	}
//	return ret
//}

//import (
//"strings"
//)
//
//func mySort(path [][]int) {
//	for i := 0; i < len(path); i++ {
//		temp := 0
//		for j := 0; j < len(path)-i; j++ {
//			if path[temp][0] < path[j][0] {
//				temp = j
//			}
//		}
//		_temp := path[len(path)-i-1]
//		path[len(path)-i-1] = path[temp]
//		path[temp] = _temp
//	}
//}

//func back(pos []int, m [][][]int, n int, key []string, path [][]int, ret *[]int) {
//
//	if len(key) == n {
//		tempPath := make([][]int, len(path))
//		for i := 0; i < len(path); i++ {
//			tempPath[i] = path[i]
//		}
//
//		mySort(tempPath)
//		for i := 1; i < len(tempPath); i++ {
//			if tempPath[i-1][1]+1 != tempPath[i][0] {
//				return
//			}
//		}
//		*ret = append(*ret, tempPath[0][0])
//		return
//	}
//
//	for i := 0; i < len(m[n]); i++ {
//		path = append(path, m[n][i])
//		back(m[n][i], m, n+1, key, path, ret)
//		path = path[0 : len(path)-1]
//	}
//}

//func getAllSubStr(str string, word string) [][]int {
//	id := 0
//	pos := make([][]int, 0)
//	temp := ""
//	for id < len(str) {
//		temp = str[id:]
//		ret := strings.Index(temp, word)
//		if ret < 0 {
//			break
//		}
//		pos = append(pos, []int{id + ret, id + ret + len(word) - 1})
//		id += 1
//	}
//
//	for i := 0; i < len(pos)-1; i++ {
//		for j := i + 1; j < len(pos); {
//			if pos[i][0] == pos[j][0] && pos[i][1] == pos[j][1] {
//				copy(pos[j:], pos[j+1:])
//				pos = pos[:len(pos)-1]
//				continue
//			}
//			j++
//		}
//	}
//
//	return pos
//}

//func findSubstring(s string, words []string) []int {
//	pos := make([][][]int, len(words))
//	for i := 0; i < len(words); i++ {
//		ret := getAllSubStr(s, words[i])
//		pos[i] = ret
//	}
//	ret := make([]int, 0)
//	back([]int{}, pos, 0, words, [][]int{}, &ret)
//	dupM := make(map[int]uint8)
//	for i := 0; i < len(ret); i++ {
//		if _, ok := dupM[ret[i]]; ok {
//			copy(ret[i:], ret[i+1:])
//			ret = ret[:len(ret)-1]
//			i--
//			continue
//		}
//		dupM[ret[i]] = 1
//	}
//	return ret
//}
